package com.mg.simulate;

import java.io.Serializable;
import java.util.*;
import java.util.function.Consumer;
import java.util.stream.Stream;

public class MyArrayList<E> extends AbstractList<E> implements Serializable, RandomAccess, Cloneable {

    /**
     * 默认初始容量
     */
    private static final int DEFAULT_CAPACITY = 10;

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * 空对象数组，当初始化集合时，传入的指定数量为0时使用
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 真正存储元素的数组，不参与序列化
     */
    transient Object[] elementData;

    /**
     * 集合中元素的数量
     */
    private int size;

    /**
     * 修改次数的统计
     */
    protected transient int modCount = 0;

    /**
     * 三种构造方式：指定大小
     * @param initialCapacity
     */
    public MyArrayList(int initialCapacity) {
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            this.elementData = new Object[initialCapacity];
        }
    }

    /**
     * 三种构造方式：不指定大小，以空对象数组初始化，在第一次添加元素时，会将容量扩充为DEFAULT_CAPACITY，即10
     */
    public MyArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * 三种构造方式：将另一个集合以Iterate遍历的顺序添加到当前集合中
     * @param c
     */
    public MyArrayList(Collection<? extends E> c) {
        //TODO
    }

    @Override
    public boolean add(E element) {
        //检查是否需要扩容
        ensureCapacityInternal(size + 1);
        elementData[size++] = element;
        return true;
    }

    private void ensureCapacityInternal(int minCapacity) {
        int capacity = calculateCapacity(elementData, minCapacity);
        ensureExplicitCapacity(capacity);
    }


    /**
     * index的范围为[0-size]，闭区间
     * @param index
     * @param element
     */
    @Override
    public void add(int index, E element) {
        //TODO 检查索引是否越界
        rangeCheckForAdd(index);

        //检查是否需要扩容
        ensureCapacityInternal(size + 1);

        //把index往后的元素依次往后移动
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        //将element插入到index的位置
        elementData[index] = element;
        //数组的大小加1
        size++;
    }


    @Override
    public boolean addAll(Collection<? extends E> c) {
        //TODO

        return false;
    }

    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0) {
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    }

    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //按照最大值取，只需要扩容一次，若按照最小值取，则需要多次扩容
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }


    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        if (minCapacity > elementData.length) {
            //对elementData进行扩容
            grow(minCapacity);
        }
    }

    /**
     * 按照1.5倍的速度扩容
     * 若扩容后的容量小于指定容量MAX_ARRAY_SIZE，则返回指定容量
     * 若超出MAX_ARRAY_SIZE，则返回Integer.MAX_VALUE
     * @param minCapacity
     */
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity < minCapacity) {
            newCapacity = minCapacity;
        }
        if (newCapacity > MAX_ARRAY_SIZE) {
            newCapacity = hugeCapacity(minCapacity);
        }

        System.out.println("扩容过后，newCapacity = " + newCapacity);

        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    /**
     * 如果容量超出默认的最大值MAX_ARRAY_SIZE，则按照Integer的最大值处理
     * @param minCapacity
     * @return
     */
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) {
            throw new OutOfMemoryError();
        }
        return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
    }

    @Override
    public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    }


    E elementData(int index) {
        return (E) elementData[index];
    }


    private void rangeCheck(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    }

    @Override
    public E remove(int index) {

        //1、检查索引是否越界；
        //2、获取指定索引位置的元素；
        //3、如果删除的不是最后一位，则其它元素往前移一位；
        //4、将最后一位置为null，方便GC回收；
        //5、返回删除的元素。
        rangeCheck(index);
        modCount++;
        E removeValue = elementData(index);

        //如果删除的元素不是最后的位置(size-1)，则index后面的元素，都要依次往前移动一位
        if (index < size - 1) {
            System.arraycopy(elementData, index+1, elementData, index, size - 1 - index);
        }

        elementData[--size] = null;
        return removeValue;
    }

    @Override
    public boolean remove(Object o) {
        if(o == null) {
            for (int i = 0; i < size; i++) {
                if (elementData[i] == null) {
                    fastRemove(i);
                    return true;
                }
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (o.equals(elementData[i])) {
                    fastRemove(i);
                    return true;
                }
            }
        }
        return false;
    }


    /**
     * 不需要进行数组越界的检查
     * @param index
     */
    private void fastRemove(int index) {
        modCount++;

        if (index < size - 1) {
            System.arraycopy(elementData, index + 1, elementData, index, size - 1 - index);
        }
        elementData[--size] = null;
    }

    @Override
    public void forEach(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        final int expectedModCount = modCount;
        @SuppressWarnings("unchecked")
        final E[] elementData = (E[]) this.elementData;
        final int size = this.size;
        for (int i=0; modCount == expectedModCount && i < size; i++) {
            action.accept(elementData[i]);
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }


    /**
     * 求两个集合的交集
     * @param c
     * @return
     */
    @Override
    public boolean retainAll(Collection<?> c) {
        if (CommUtil.isEmpty(c)) {
            throw new NullPointerException();
        }
        //1、调用批量删除方法，这时complement传入true，表示删除不包含在c中的元素
        return batchRemove(c, true);
    }


    @Override
    public boolean removeAll(Collection<?> c) {
        // 集合c不能为空
        Objects.requireNonNull(c);
        // 同样调用批量删除方法，这时complement传入false，表示删除包含在c中的元素
        return batchRemove(c, false);
    }

    /**
     * 批量删除元素
     * complement为true表示删除c中不包含的元素
     * complement为false表示删除c中包含的元素
     */
    private boolean batchRemove(Collection<?> c, boolean complement) {

        Object[] elementData = this.elementData;

        int r = 0;
        int w = 0;
        boolean modified = false;

        try {
            //1、遍历elementData数组；
            for (; r < size; r++) {
                if (c.contains(elementData[r]) == complement) {
                    elementData[w++] = elementData[r];
                }
            }
        } finally {
            if (r != size) {
                System.arraycopy(elementData, r, elementData, w, size - r);
                w += size - r;
            }

            if (w != size) {
                for (int i = w; i < size; i++) {
                    elementData[i] = null;
                }

                modCount += (size - w);
                size = w;
                modified = true;
            }

        }
        return modified;
    }

    @Override
    public Stream<E> stream() {
        return null;
    }

    @Override
    public Stream<E> parallelStream() {
        return null;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public void sort(Comparator<? super E> c) {

    }
}